package _dp_base;

/**
 * 309. 买卖股票的最佳时机含冷冻期
 */
public class No309 {
    private int[] prices;

    /**
     * 1. 递归
     */
    public int maxProfit1(int[] prices) {
        this.prices = prices;
        int n = prices.length;

        return Math.max(dfs(n - 1, 0), dfs(n - 1, 2));
    }

    private int dfs(int i, int hold) {
        if (i < 0) return hold == 0 ? 0 : Integer.MIN_VALUE;
        else if (hold == 0) return Math.max(dfs(i - 1, 2), dfs(i - 1, 0));
        else if (hold == 1) return Math.max(dfs(i - 1, 1), dfs(i - 1, 0) - prices[i]);
        else return dfs(i - 1, 1) + prices[i];

    }

    /**
     * 2. 迭代
     */
    public int maxProfit2(int[] prices) {
        int n = prices.length;
        int[][] f = new int[n + 1][3];
        f[0][1] = Integer.MIN_VALUE;
        f[0][2] = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            f[i + 1][0] = Math.max(f[i][2], f[i][0]);
            f[i + 1][1] = Math.max(f[i][1], f[i][0] - prices[i]);
            f[i + 1][2] = f[i][1] + prices[i];
        }
        return Math.max(f[n][0], f[n][2]);
    }

    /**
     * 4. 一维数组
     */
    public int maxProfit4(int[] prices) {
        int[] f = new int[3];
        f[1] = Integer.MIN_VALUE;
        f[2] = Integer.MIN_VALUE;
        for (int price : prices) {
            int temp0, temp1, temp2;
            temp0 = Math.max(f[2], f[0]);
            temp1 = Math.max(f[1], f[0] - price);
            temp2 = f[1] + price;
            f[0] = temp0;
            f[1] = temp1;
            f[2] = temp2;
        }
        return Math.max(f[0], f[2]);
    }
}
